#
# @lc app=leetcode.cn id=542 lang=python3
#
# [542] 01 矩阵
#

# @lc code=start
from collections import deque
from typing import List


class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        v = len(matrix)
        h = len(matrix[0])
        ans = [[-1] * h for _ in range(v)]
        dq = deque()

        n = h * v
        for i in range(v):
            for j in range(h):
                if matrix[i][j] == 0:
                    ans[i][j] = 0
                    dq.append((i, j))
                    n -= 1

        while n:
            i, j = dq.popleft()
            for mi, mj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if -1 < mi < v and -1 < mj < h and ans[mi][mj] == -1:
                    ans[mi][mj] = ans[i][j] + 1
                    dq.append((mi, mj))
                    n -= 1

        return ans


# @lc code=end
